package leetcode;

/**
 * Created by Ghost on 2014/11/17 0017.
 */
public class Reverse_Linked_List_II {
    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur.next != null) {
            ListNode tmp;
            if (cur == head) {
                tmp = cur.next;
                cur.next = null;
                cur = tmp;
                pre = head;
            } else {
                tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }

        }
        cur.next = pre;
        return cur;
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null)
            return null;
        ListNode pre = null;
        ListNode cur = head;
        int count = 0;
        ListNode M = null, N = null;
        ListNode MP = null, AN = null;
        while (cur != null) {
            count++;
            if (count == m) {
                MP = pre;
                M = cur;
            }
            if (count == n) {
                AN = cur.next;
                N = cur;
                N.next = null;
                break;
            }
            pre = cur;
            cur = cur.next;
        }


        ListNode newHead = reverseList(M);
        ListNode tmp = newHead;
        while (tmp.next != null)
            tmp = tmp.next;
        tmp.next = AN;

        if (MP == null) {
            return newHead;
        } else {
            MP.next = newHead;
            return head;
        }
    }
    public static void main(String[] args){
        Reverse_Linked_List_II reverse_linked_list_ii = new Reverse_Linked_List_II();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode newhead = reverse_linked_list_ii.reverseBetween(head,2,3);
        while(newhead!=null){
            System.out.println(newhead.val);
            newhead = newhead.next;
        }
    }
}
